/**
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
 */

(function () {
    /**
     * 解法： 按map值进行判断
     * @description 根据s1长度生成的map，遍历s2，滑动窗口设定为计算字符串个数的map，通过map的值是否相等进行判断
     * 题目要求s1 的排列之一是 s2 的 子串，则表示s1与s2的滑动窗口长度相等，字符串相等 => 长度相等，包含的每个小写字符的个数也是相等的
     * 1. 设定s1的map，根据 a~z 生成map，形如：{ a: 0, b: 0 ....}
     * 2. 设定s2的初始map: winMap，根据 a~z 生成map，长度与s1相同，开始位置为s2的开头部分
     * 3. 若s1与s2的初始map相等，则直接返回true
     * 4. 从s1 length的位置遍历s2，每右移一个字符，winMap的当前对应值 + 1，同时winMap的开头字符的对应值 - 1(窗口右移)
     * 5. 直到遍历出结果，若s1Map与winMap没有相等的情况，则返回false
     * @param s1
     * @param s2
     * @returns
     */
    function checkInclusion(s1: string, s2: string): boolean {
        if (s1.length > s2.length) return false;
        else if (s1.length > Math.pow(10, 4) || s2.length > Math.pow(10, 4))
            return false;
        else if (s1.length < 1 || s2.length < 1) return false;
        const checkLength = s1.length;
        const s1Arr = Array.from(s1);
        const s2Arr = Array.from(s2);
        // 设置s1Map
        const s1Map = initStrHash(s1Arr);
        // 设置winMap, 初始值为s2的开头部分
        const winMap = initStrHash(s2Arr.slice(0, checkLength));
        // 初始即相等，则返回true
        if (
            [...s1Map.values()].toString() === [...winMap.values()].toString()
        ) {
            return true;
        }
        // 遍历s2
        for (let i = checkLength; i < s2Arr.length; i++) {
            // 每右移一个字符，winMap的当前对应值+1，同时winMap的开头字符串的对应值-1
            const cur = s2Arr[i];
            const first = s2Arr[i - checkLength];
            winMap.set(cur, winMap.get(cur) + 1);
            winMap.set(first, winMap.get(first) - 1);
            if (
                [...s1Map.values()].toString() ===
                [...winMap.values()].toString()
            ) {
                return true;
            }
        }
        return false;
    }

    function initStrHash(strArr: string[]) {
        let map = new Map();
        for (let i = 0; i < 26; i++) {
            map.set(String.fromCharCode("a".charCodeAt(0) + i), 0);
        }

        for (let i = 0; i < strArr.length; i++) {
            const str = strArr[i];
            if (map.has(str)) {
                map.set(str, map.get(str) + 1);
            } else {
                map.set(str, 1);
            }
        }
        return map;
    }

    console.log(
        "checkInclusion(hello, ooolleoooleh):",
        checkInclusion("hello", "ooolleoooleh")
    );
})();
